And of course, the third thing we could do is use local search by starting with a complete

assignment that possibly violates constraints and then just reassign variables in our assignment

such that until we have found an assignment that doesn't violate any constraints.

And of course, there are some heuristics here we can use in the sense of which variables

do we pick for reassignment first and which values do we select.

The most obvious way to do this is by basically just picking out a random variable and assigning

a value to it that has the least amount of violations of constraints.

Here is an example where we could do something like that for a queen's problems.

We start with some random assignment that violates lots of constraints.

Then we pick out any queen in this case, the second one, and just move it somewhere where

it violates as few constraints as possible.

In this case, there is even one position where it doesn't violate any constraints.

So we just take that queen and move it over here.

And then we do the same thing with, in this case, the third queen, move that down here.

So it again doesn't violate any constraints and then we have found a solution.

This way you can basically use all of the algorithm we've talked about with respect

to local search.

So hill climbing, you can use simulated annealing and all of those.

So all of these techniques we already know we can then throw at constraint satisfaction

problems as well.

There is this interesting tidbit here that it happens to be the case that if the ratio

of numbers of constraints in our constraint network over the number of variables approaches

a certain critical ratio, then suddenly the computational effort required to solve the

problem grows extremely, where everywhere else it's rather efficient in general.

It's just this one small narrow where local search happens to be weirdly inefficient.

What a pity that it doesn't actually say what number this is.

Not that it's too important, but yeah.